package _06_动态规划;

public class _918_环形子数组的最大和 {

    public static void main(String[] args) {
        _918_环形子数组的最大和 v = new _918_环形子数组的最大和();

        int[] ins = {-2};
        System.out.println(v.maxSubarraySumCircular(ins));

    }

    // 两种情况，一种是最大元素在中间，另一种是最大元素在两边
    // 第二种情况者是找到最小的元素
    // 如果出现覆盖的情况中间记录最大值
    public int maxSubarraySumCircular(int[] nums) {
        // 寻找最大的子序列和
        int max, curMax, min, curMin, sum;
        max = curMax = min = curMin = sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum += nums[i];
            curMax = Math.max(nums[i], curMax + nums[i]);
            max = Math.max(max, curMax);
            curMin = Math.min(nums[i], curMin + nums[i]);
            min = Math.min(min, curMin);
        }
        if (max < 0) return max;
        return Math.max(max, sum - min);
    }

}
